package com.example.myspringboot.test;

import java.util.HashMap;
import java.util.Map;

public class Trie {
    private final Map<String, Boolean> stringMap;

    public Trie() {
        stringMap = new HashMap<>();
    }

    // 插入操作
    public void insert(String str) {
        stringMap.put(str, true);
    }

    // 搜索操作
    public boolean search(String str) {
        return stringMap.containsKey(str);
    }

    // 删除操作
    public boolean delete(String str) {
        return stringMap.remove(str) != null;
    }

    // 分析：
    // 时间复杂度：
    // - 插入：O(1) 平均情况，O(n) 最坏情况（n是键的哈希冲突数）
    // - 搜索：O(1) 平均情况，O(n) 最坏情况
    // - 删除：O(1) 平均情况，O(n) 最坏情况
    //
    // 空间复杂度：
    // - O(N)，其中N是存储在数据结构中的不同字符串的数量。每个字符串都需要一个哈希表条目来存储。
    //
    // 设计选择解释：
    // 我们选择HashMap是因为它提供了平均情况下接近O(1)的搜索、插入和删除操作，这在处理大量数据时非常高效。
    // HashMap通过哈希函数将键映射到桶（或槽）的索引，并在每个桶中存储一个链表或红黑树来处理哈希冲突。
    // 通过调整初始容量和加载因子，我们可以优化HashMap的性能以适应特定的用例。
}
